1993C - Light Switches - CodeForces Solution

def get_input():
    t = int(input())
    cases = []
    for _ in range(t):
        n, k = map(int, input().split(" "))
        a = list(map(int, input().split(" ")))

        cases.append((n, k, a))

    return cases

def get_result(n, k, a):
        m = max(a) + k
        size = 2 * k
        min_start = float("inf")
        max_start = 0
        for i in range(n):
            c = (m - a[i]) // size
            a[i] += size * c

            min_start = min(min_start, a[i])
            max_start = max(max_start, a[i])
            
            if max_start - min_start >= k:
                return -1

        return int(max_start)


def main():
    inputs = get_input()    

    for (n, k, a) in inputs:        
        print(get_result(n, k, a))

if __name__ == '__main__':
    main()